package a09_贪心算法;

/**
 * <p>
 * a08_跳跃游戏2
 * </p>
 *
 * @author flyduck
 * @since 2025/1/10
 */
public class a08_跳跃游戏2 {
    public static void main(String[] args) {
        a08_跳跃游戏2 test = new a08_跳跃游戏2();
        test.jump(new int[]{2,1});
    }
    //逻辑：2,3,1,1,4
    //在idx=0的时候，覆盖范围是2
    //我们计算下一步最大的覆盖范围=4
    //把第一步也当作循环
    public int jump(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int currentCover = nums[0];//当前覆盖范围

        int nextMaxCover = Integer.MIN_VALUE;//下一步最大覆盖范围
        int result = 1;//具体跳几步
        int nextIdx = 1;//下一步的索引
        if(currentCover >= nums.length - 1){
            return result;
        }
        while (nextIdx <= currentCover) {
            nextMaxCover = Math.max(nextMaxCover, nextIdx + nums[nextIdx]);//计算下一步最大覆盖范围
            if(nextIdx == currentCover){//走到当前覆盖范围的终点
                if(nextIdx != nums.length - 1) {//走到当前覆盖范围的终点，但是没有走到数组的最后，继续要走
                    result++;//走一步
                    currentCover = nextMaxCover;//更新当前的覆盖范围
                    if(currentCover >= nums.length - 1){
                        return result;
                    }
                }else {
                    return result;
                }
            }else {
                nextIdx++;
            }
        }
        return result;
    }
}
